home *** CD-ROM | disk | FTP | other *** search
/ Aminet 40 / Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso / Aminet / dev / lang / Python16_Src.lha / Python16_Source / Parser / acceler.c next >
Encoding:
C/C++ Source or Header  |  2000-08-03  |  3.2 KB  |  150 lines
  1. /* Parser accelerator module */
  2.  
  3. /* The parser as originally conceived had disappointing performance.
  4.    This module does some precomputation that speeds up the selection
  5.    of a DFA based upon a token, turning a search through an array
  6.    into a simple indexing operation.  The parser now cannot work
  7.    without the accelerators installed.  Note that the accelerators
  8.    are installed dynamically when the parser is initialized, they
  9.    are not part of the static data structure written on graminit.[ch]
  10.    by the parser generator. */
  11.  
  12. #include "pgenheaders.h"
  13. #include "grammar.h"
  14. #include "node.h"
  15. #include "token.h"
  16. #include "parser.h"
  17.  
  18. /* Forward references */
  19. static void fixdfa Py_PROTO((grammar *, dfa *));
  20. static void fixstate Py_PROTO((grammar *, state *));
  21.  
  22. void
  23. PyGrammar_AddAccelerators(g)
  24.     grammar *g;
  25. {
  26.     dfa *d;
  27.     int i;
  28. #ifdef Py_DEBUG
  29.     fprintf(stderr, "Adding parser accelerators ...\n");
  30. #endif
  31.     d = g->g_dfa;
  32.     for (i = g->g_ndfas; --i >= 0; d++)
  33.         fixdfa(g, d);
  34.     g->g_accel = 1;
  35. #ifdef Py_DEBUG
  36.     fprintf(stderr, "Done.\n");
  37. #endif
  38. }
  39.  
  40. void
  41. PyGrammar_RemoveAccelerators(g)
  42.     grammar *g;
  43. {
  44.     dfa *d;
  45.     int i;
  46.     g->g_accel = 0;
  47.     d = g->g_dfa;
  48.     for (i = g->g_ndfas; --i >= 0; d++) {
  49.         state *s;
  50.         int j;
  51.         s = d->d_state;
  52.         for (j = 0; j < d->d_nstates; j++, s++) {
  53.             if (s->s_accel)
  54.                 PyMem_DEL(s->s_accel);
  55.             s->s_accel = NULL;
  56.         }
  57.     }
  58. }
  59.  
  60. static void
  61. fixdfa(g, d)
  62.     grammar *g;
  63.     dfa *d;
  64. {
  65.     state *s;
  66.     int j;
  67.     s = d->d_state;
  68.     for (j = 0; j < d->d_nstates; j++, s++)
  69.         fixstate(g, s);
  70. }
  71.  
  72. static void
  73. fixstate(g, s)
  74.     grammar *g;
  75.     state *s;
  76. {
  77.     arc *a;
  78.     int k;
  79.     int *accel;
  80.     int nl = g->g_ll.ll_nlabels;
  81.     s->s_accept = 0;
  82.     accel = PyMem_NEW(int, nl);
  83.     for (k = 0; k < nl; k++)
  84.         accel[k] = -1;
  85.     a = s->s_arc;
  86.     for (k = s->s_narcs; --k >= 0; a++) {
  87.         int lbl = a->a_lbl;
  88.         label *l = &g->g_ll.ll_label[lbl];
  89.         int type = l->lb_type;
  90.         if (a->a_arrow >= (1 << 7)) {
  91.             printf("XXX too many states!\n");
  92.             continue;
  93.         }
  94.         if (ISNONTERMINAL(type)) {
  95.             dfa *d1 = PyGrammar_FindDFA(g, type);
  96.             int ibit;
  97.             if (type - NT_OFFSET >= (1 << 7)) {
  98.                 printf("XXX too high nonterminal number!\n");
  99.                 continue;
  100.             }
  101.             for (ibit = 0; ibit < g->g_ll.ll_nlabels; ibit++) {
  102.                 if (testbit(d1->d_first, ibit)) {
  103. #ifdef applec
  104. #define MPW_881_BUG            /* Undefine if bug below is fixed */
  105. #endif
  106. #ifdef MPW_881_BUG
  107.                     /* In 881 mode MPW 3.1 has a code
  108.                        generation bug which seems to
  109.                        set the upper bits; fix this by
  110.                        explicitly masking them off */
  111.                     int temp;
  112. #endif
  113.                     if (accel[ibit] != -1)
  114.                         printf("XXX ambiguity!\n");
  115. #ifdef MPW_881_BUG
  116.                     temp = 0xFFFF &
  117.                         (a->a_arrow | (1 << 7) |
  118.                          ((type - NT_OFFSET) << 8));
  119.                     accel[ibit] = temp;
  120. #else
  121.                     accel[ibit] = a->a_arrow | (1 << 7) |
  122.                         ((type - NT_OFFSET) << 8);
  123. #endif
  124.                 }
  125.             }
  126.         }
  127.         else if (lbl == EMPTY)
  128.             s->s_accept = 1;
  129.         else if (lbl >= 0 && lbl < nl)
  130.             accel[lbl] = a->a_arrow;
  131.     }
  132.     while (nl > 0 && accel[nl-1] == -1)
  133.         nl--;
  134.     for (k = 0; k < nl && accel[k] == -1;)
  135.         k++;
  136.     if (k < nl) {
  137.         int i;
  138.         s->s_accel = PyMem_NEW(int, nl-k);
  139.         if (s->s_accel == NULL) {
  140.             fprintf(stderr, "no mem to add parser accelerators\n");
  141.             exit(1);
  142.         }
  143.         s->s_lower = k;
  144.         s->s_upper = nl;
  145.         for (i = 0; k < nl; i++, k++)
  146.             s->s_accel[i] = accel[k];
  147.     }
  148.     PyMem_DEL(accel);
  149. }
  150.